package org.algorithm.落雪.数组.三月.第二周;

/**
 * <p>
 *  给你一个整数数组nums 。「数组值」定义为所有满足0 <= i < nums.length-1的|nums[i]-nums[i+1]|的和。
 *
 *  你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作一次 。
 *
 *  请你找到可行的最大 数组值。
 *</p>
 *  * 困难题   *
 * @author 落雪
 * @date 2022/3/06   星期日
 * uri:  https://leetcode-cn.com/problems/reverse-subarray-to-maximize-array-value/
 */
public class 反转子数组取最大值 {

    public static void main(String[] args) {
        int[] nums = {2,4,9,24,2,1,10};
        System.out.println(maxValueAfterReverse(nums));
    }


    public static int maxValueAfterReverse(int[] nums) {

        int total = 0;
        int n = nums.length;
        int hi = Integer.MIN_VALUE;
        int gain = 0;
        int low = Integer.MAX_VALUE;
        for(int i = 0; i < n - 1; i++){
            int n1 = nums[i];
            int n2 = nums[i + 1];
            int diff = Math.abs(n1 - n2);
            total += diff;
            hi = Math.max(hi, Math.min(n1, n2));
            low = Math.min(low, Math.max(n1, n2));
            gain = Math.max(gain, Math.abs(nums[0] - nums[i + 1]) - diff);
            gain = Math.max(gain, Math.abs(nums[n - 1] - nums[i]) - diff);
        }
        int addition = Math.max(0, 2 * (hi - low));
        return(Math.max(gain, addition) + total);
    }
}
